/**
 * 二分查找的思路分析,注意，二分查找的数组是有序的
  1.首先确定该数组的中间的下标
  mid = (left+right)/2
  2.然后让需要查找的数 findVal和arr[mid]比较
  2.1 findVal>arr[mid],说明你要查找的数在mid的右边，
  因此需要递归的向右查找
  2.2 findVal<arr[mid],说明你要查找的数在mid的左边，
  因此需要递归的向左查找
  2.3 findVal === arr[mid]说明找到，就返回

  什么时候需要结束递归
  1.找到就结束递归
  2.递归完整个数组，仍然没有找到findVal,也需要结束递归
  当left>right就需要退出
 */
/**
 * 
 * @param {数组} arr 
 * @param {左边的索引} left 
 * @param {右边的索引} right 
 * @param {*要找的值} findVal
 * @return 如果找到就返回下标，如果没找到就返回-1 
 */
function binarySearch(arr, left, right, findVal) {
    //当left>right时，就没找到，结束
    if (left > right) {
        return -1
    }

    let mid = Math.floor((left + right) / 2);
    let midVal = arr[mid];

    if (findVal > midVal) {
        //向右递归
        return binarySearch(arr, mid + 1, right, findVal);
    } else if (findVal < midVal) {
        //向左递归
        return binarySearch(arr, left, mid - 1, findVal);
    } else {
        return mid;
    }
}

/**
 * while方法
 */
function binary_search(arr,key){
  var low=0,
      high=arr.length-1;
  while(low<=high){
    var mid=parseInt((high+low)/2);
    console.log('arr[mid]'+arr[mid]+',key:'+key)
    console.log(key>arr[mid])
    if(key===arr[mid]){
        return mid
     }
    else if(key>arr[mid]){
      low=mid+1
    }
    else if(key<arr[mid]){
      high=mid-1
    }
  }
  return -1
}
var _arr=[1,5,6,7,8,10,11]
    
var t=binary_search(_arr,0)
console.log('索引值:'+t)